// CSE-102 DSA Assignment - Implementation of the python's list functions in C (Linked List Implementation).
// Ankit Mittal - 2010015

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct list{	int index;
				int type;
				union content{	char * ch;
						int i;
						float f;
		  			     }data;
  	 			struct list * next;
   		   }*start=NULL, *rear=NULL, *ptr, *temp, *prev;

int in=0;									//Largest index in the list.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void inputlist()
{	int x=99;
	char terminator='a';
	printf("Enter the list elements seperated by a comma without asing any white spaces: ");
	while(terminator!='\n')
	{	scanf("%d",&x);
		scanf("%c",&terminator);		
		ptr=malloc(sizeof(struct list));
		ptr->index=in;
		ptr->data.i=x;
		ptr->next=NULL;
		if(start==NULL)
		{	start=ptr;
			rear=ptr;
		}
		else
		{	rear->next=ptr;
			rear=ptr;	
		}
		in++;
	}
	in--;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void printlist(struct list * begin)
{	ptr=begin;
	printf("\nRequired List: [");
	if(ptr!=NULL)
	{	printf("%d",ptr->data.i);
		ptr=ptr->next;
	}
	while(ptr!=NULL)
	{	printf(", %d",ptr->data.i);
		ptr=ptr->next;
	}
	printf("]\n");
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void slicing()
{	int n1,n2;
	printf("\nEnter the slice indeces seperated by a colon: ");
	scanf("\n%d:%d",&n1,&n2);
	if(n1<0)
		n1=in+n1+1;
	if(n2<0)
		n2=in+n2+1;
	if(n1>=n2||n1>in)
	{	printf("\nSliced portion of the List: []\n");
		return;
	}
	printf("\nSliced portion of the List: [");
	ptr=start;
	while(ptr!=NULL && ptr->index<n2)
	{	if(ptr->index==n1)
			printf("%d",ptr->data.i);
		else if(ptr->index>n1)
			printf(", %d",ptr->data.i);
		ptr=ptr->next;
	}
	printf("]\n");
	return;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void transversing()
{	int n1;
	printf("\nEnter the index: ");
	scanf("\n%d",&n1);
	if(n1<0)
		n1=in+n1+1;
	if(n1>in||n1<0)
	{	printf("\nNo such index...");
		return;
	}
	printf("\nRequired Element: ");
	ptr=start;
	while(ptr!=NULL)
	{	if(ptr->index==n1)
		{	printf("%d\n",ptr->data.i);
			break;
		}
		ptr=ptr->next;
	}
	return;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void reverse()
{	
	for(ptr=start,prev=NULL,rear=start;ptr!=NULL;prev=ptr,ptr=temp)
	{	if(ptr->next==NULL)
		{	ptr->next=prev;
			temp=NULL;
		}
		
		else
		{	temp=ptr->next;
			ptr->next=prev;
		}
	}
	start=prev;
	
	for(ptr=start,in=0;ptr!=NULL;ptr=ptr->next)
	{	ptr->index=in++;
	}
	in--;
	printlist(prev);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void append()
{	int ele;
	printf("\nEnter the element to be inserted: ");
	scanf("\n%d",&ele);
	ptr=malloc(sizeof(struct list));
	if(start==NULL)
	{	ptr->data.i=ele;
		ptr->next=NULL;
		ptr->index=++in;
		start=rear=ptr;
	}
	else
	{	ptr->data.i=ele;
		ptr->next=NULL;
		rear->next=ptr;
		rear=ptr;
		ptr->index=++in;
	}
	printlist(start);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void sort()
{	int x;
	struct list *p, *pr, *nx;
	for(ptr=start;ptr->next!=NULL;ptr=ptr->next)
	{	for(p=start,nx=p->next;p->next!=NULL;p=p->next,nx=nx->next)
		{	if((p->data.i)>(nx->data.i))
				{	x=p->data.i;
					p->data.i=nx->data.i;
					nx->data.i=x;	
				}			

		}
		prev=pr;

	}
	printlist(start);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void removing()
{	int ele;
	printf("\nEnter the element whose first occurence has to be removed: ");
	scanf("\n%d",&ele);
	for(ptr=start,prev=NULL;ptr!=NULL;prev=ptr,ptr=ptr->next)
	{	if(ptr->data.i==ele)
		{	if(ptr==start)
			{	if(start->next==NULL)
				{	rear=start;
					start=NULL;
					in--;
					break;
				}
				else
				{	start=ptr->next;
					for(ptr=ptr->next;ptr!=NULL;ptr=ptr->next)
					{	ptr->index-=1;
					}
					in--;
					free(ptr);
					break;
				}
			}
			else
			{	if(ptr==rear)
				{	rear=prev;
					rear->next=NULL;
					ptr=NULL;
					free(ptr);
					in--;
					break;
				}
				else
				{	prev->next=ptr->next;
					for(ptr=ptr->next;ptr!=NULL;ptr=ptr->next)
					{	ptr->index-=1;
					}
					in--;
					free(ptr);
					break;
				}
			}
		}
	}
	printlist(start);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
void count()
{	int ele;
	int cnt=0;
	printf("\nEnter the element whose number of ocuurances you want to count: ");
	scanf("\n%d",&ele);
	for(ptr=start;ptr!=NULL;ptr=ptr->next)
		{	if(ptr->data.i==ele)
				cnt+=1;
		}
	printf("\n%d appears %d times in the list.",ele,cnt);
	
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void indexing()
{	int ele;
	int i;
	printf("\nEnter the element, the index of whose first occurence has to be returned: ");
	scanf("\n%d",&ele);
	for(ptr=start;ptr!=NULL;ptr=ptr->next)
	{	if(ptr->data.i==ele)
		{	i=ptr->index;
			printf("\nElement %d first occurs at index %d",ele,i);
			break;
		}
	}
	if(ptr==NULL)
	{	printf("\n No such element...");	
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void insert()
{	int ele;
	int pos;
	struct list * newptr=malloc(sizeof(struct list));
	newptr->next=NULL;
	printf("\nEnter the insertion index and the value to be inserted in the i,x format: ");
	scanf("\n%d,%d",&pos,&ele);
	if(pos<0)
	{	pos=in+pos+2;
	}
	if(pos>in+1||pos<0)
		{	printf("\nIndex not reachable...\n");
		}
	else
	{	for(ptr=start;ptr!=NULL;ptr=ptr->next)
		{	if(pos==0)
			{	newptr->index=pos;
				newptr->data.i=ele;
				newptr->next=start;
				start=newptr;
				break;
			}
			else if(ptr->index==pos-1)
			{	newptr->index=pos;
				newptr->data.i=ele;
				newptr->next=ptr->next;
				ptr->next=newptr;
				break;
			}
		}
		for(ptr=newptr->next;ptr!=NULL;ptr=ptr->next)
		{	ptr->index+=1;
		}
		in++;
		printlist(start);
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void extend()
{	struct list * newptr;
	int x=99;
	char terminator='a';
	printf("\nEnter the list elements seperated by a comma without asing any white spaces: ");
	while(terminator!='\n')
	{	scanf("%d",&x);
		scanf("%c",&terminator);		
		ptr=malloc(sizeof(struct list));
		ptr->index=++in;
		ptr->data.i=x;
		ptr->next=NULL;
		if(start==NULL)
		{	start=ptr;
			rear=ptr;
		}
		else
		{	rear->next=ptr;
			rear=ptr;	
		}
	}
	printlist(start);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
void poping()
{	int i;
	int ele;
	printf("\nEnter the index of the element to be deleted: ");
	scanf("\n%d",&i);
	if(i<0)
	{	i=in+i+1;
	}
	if(i<0||i>in)
	{	printf("\nIndex not reachable...\n");
		return;
	}
	for(ptr=start,prev=NULL;ptr!=NULL;prev=ptr,ptr=ptr->next)
	{	if(ptr->index==i)
		{	if(ptr==start)
			{	if(start->next==NULL)
				{	rear=start;
					start=NULL;
					in--;
					break;
				}
				else
				{	start=ptr->next;
					for(ptr=ptr->next;ptr!=NULL;ptr=ptr->next)
					{	ptr->index-=1;
					}
					in--;
					free(ptr);
					break;
				}
			
			}
			else
			{	if(ptr==rear)
				{	rear=prev;
					rear->next=NULL;
					ptr=NULL;
					free(ptr);
					in--;
					break;
				}
				else
				{	prev->next=ptr->next;				
					for(ptr=ptr->next;ptr!=NULL;ptr=ptr->next)
					{	ptr->index-=1;
					}
					in--;
					free(ptr);
					break;
				}
			}
		}
	}
	printlist(start);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
void length()
{	printf("\nThe length of the list is %d.",in+1);
}	

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{	char op;
	char more;
	start=NULL;
	rear=NULL;
	inputlist();
	printlist(start);
	do
	{	printf("\n\nR-Reversal\tI-Indexing\tL-Length\tS-Slicing");
		printf("\nQ-Sorting\tX-Removing\tJ-Insert\tP-Pop");
		printf("\nA-Append\tE-Extend\tT-Transversing");
		printf("\nC-Count\t\tD-Display");
		printf("\n\nEnter the list operation: ");
		scanf("\n%c",&op);
		switch(op)
		{	case('T'):  transversing();
  						break;
			case('S'):  slicing();
						break;
			case('R'):  reverse();
						break;
			case('A'):  append();
						break;
			case('Q'):  sort();
						break;
			case('X'):  removing();
						break;
			case('C'):  count();
						break;
			case('I'):  indexing();
						break;
			case('J'):  insert();
						break;
			case('E'):  extend();
						break;
			case('P'):  poping();
						break;
			case('L'):  length();
						break;
			case('D'):  printlist(start);
						break;
			case('t'):  transversing();
  						break;
			case('s'):  slicing();
						break;
			case('r'):  reverse();
						break;
			case('a'):  append();
						break;
			case('q'):  sort();
						break;
			case('x'):  removing();
						break;
			case('c'):  count();
						break;
			case('i'):  indexing();
						break;
			case('j'):  insert();
						break;
			case('e'):  extend();
						break;
			case('p'):  poping();
						break;
			case('l'):  length();
						break;
			case('d'):  printlist(start);
						break;
		}
		printf("\nMore operations?(y/n): ");
		scanf("\n%c",&more);
	}while(more=='y'||more=='Y');
	getchar();
	return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
